package com.leetcode.partition8;

/**
 * @author `RKC`
 * @date 2021/12/10 9:17
 */
public class LC748最短补全词 {

    public static String shortestCompletingWord(String licensePlate, String[] words) {
        int[] plateCount = new int[26];
        for (int i = 0; i < licensePlate.length(); i++) {
            char ch = licensePlate.charAt(i);
            if (Character.isLowerCase(ch)) {
                plateCount[ch - 'a']++;
            } else if (Character.isUpperCase(ch)) {
                plateCount[ch + 32 - 'a']++;
            }
        }
        int index = -1;
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            //得到word的哈希表
            int[] wordCount = new int[26];
            for (int j = 0; j < word.length(); j++) {
                char ch = word.charAt(j);
                if (Character.isLowerCase(ch)) {
                    wordCount[ch - 'a']++;
                } else if (Character.isUpperCase(ch)) {
                    wordCount[ch + 32 - 'a']++;
                }
            }
            //和plateCount进行匹配，匹配成功就返回
            if (match(plateCount, wordCount)) {
                if (index == -1) {
                    index = i;
                    continue;
                }
                if (words[index].length() > word.length()) index = i;
            }
        }
        return words[index];
    }

    private static boolean match(int[] plateCount, int[] wordCount) {
        for (int i = 0; i < 26; i++) {
            if (wordCount[i] < plateCount[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        String licensePlate = "1s3 456";
        String[] words = {"looks","pest","stew","show"};
        System.out.println(shortestCompletingWord(licensePlate, words));
    }
}
